import java.util.Arrays;

/**
 * @author ghp
 * @title
 */
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        Arrays.fill(left, -1);
        int[] right = new int[n];
        Arrays.fill(right, n);
        for (int i = 1; i < n; i++) {
            // 往左遍历，寻找第一个比当前柱子要矮的
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] < heights[i]) {
                    left[i] = j;
                    break;
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            // 往右遍历，寻找第一个比当前柱子要矮的
            for (int j = i + 1; j < n; j++) {
                if (heights[j] < heights[i]) {
                    right[i] = j;
                    break;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}